#include <iostream>
#include <algorithm>
#include <stack>
#include <unordered_set>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
#define int long long
#define ull unsigned long long 
//
//int t;
//ull a[88];
//const int mod = 1e9 + 7;
//unordered_map<ull, int> mp;
//vector<ull> pos;
//
//ull qp(int a, int b) {
//	int res = 1, base = a;
//	while (b) {
//		if (b & 1) res *= base;
//		base *= base;
//		b >>= 1;
//	}
//	return res;
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	for (int i = 2; i <= 62; i++) {
//		a[i] = (1ull << i);
//	}
//	for (int i = 2; i <= 62; i++) {
//		for (ull j = 1, l = qp(i, j), r = qp(i, j+1);; j++) {
//			if (r > a[i]) {
//				mp[max(l, a[i])] = j;
//				pos.push_back(max(l, a[i]));
//			}
//			if (r >= a[i + 1])
//				break;
//			l = r;
//			r = qp(i, j + 2);
//		}
//	}
//	for (ull i = 1,L,R; i <= t; i++) {
//		cin >> L >> R;
//		ull ans = 0;
//		int now = lower_bound(pos.begin(), pos.end(), L + 1) - pos.begin();
//		ans = (ans + ((min(pos[now] - 1, R) - L + 1) * mp[pos[now - 1]]) % mod) % mod;
//		while (pos[now] <= R) {
//			ull l = pos[now];
//			ull r = pos[now + 1];
//			ans = (ans + ((min(r - 1, R) - l + 1) * mp[l]) % mod) % mod;
//			now++;
//		}
//		cout << ans << '\n';
//	}
//	return 0;
//}

//int t;
//struct node {
//	int dis, pos;
//
//	bool operator<(const node& x)const {
//		return x.dis < dis;
//	}
//};
//
//struct egde {
//	int v, drive, walk;
//};
//
//int t0, t1, t2;
//int n, m;
//int dis[100005];
//int vis[100005];
//vector<egde> e[100005];
//
//void solve() {
//	cin >> n >> m;
//	cin >> t0 >> t1 >> t2;
//	priority_queue<node> q;
//	for (int i = 1; i <= n; i++) {
//		dis[i] = 1e18;
//		vis[i] = 0;
//		e[i].clear();
//	}
//	for (int i = 1, u, v, w1, w2; i <= m; i++) {
//		cin >> u >> v >> w1 >> w2;
//		e[u].push_back({ v,w1,w2 });
//		e[v].push_back({ u,w1,w2 });
//	}
//
//	dis[n] = 0;
//	q.push({ 0,n });
//	while (!q.empty()) {
//		node tmp = q.top();
//		int u = tmp.pos;
//		q.pop();
//		if (vis[u])continue; vis[u] = 1;
//		for (int i = 0; i < e[u].size(); i++)
//		{
//			int v = e[u][i].v;
//			int wc = e[u][i].walk;
//			int dc = e[u][i].drive;
//			if (dis[u] + dc <= t0 - t2 || dis[u] >= t0 - t1) {
//				if (!vis[v] && dis[v] > dis[u] + dc) {
//					dis[v] = dis[u] + dc;
//					q.push({ dis[v],v });
//				}
//			}
//			else if (!vis[v] && dis[v] > min(dis[u] + wc, t0 - t1 + dc)) {
//				dis[v] = min(dis[u] + wc, t0 - t1 + dc);
//				q.push({ dis[v],v });
//			}
//		}
//	}
//	cout << (t0 - dis[1] >= 0 ? t0 - dis[1] : -1) << '\n';
//}

//int n, m, k;
//void solve() {
//	cin >> n >> m >> k;
//	int ok = true;
//	if (m * 2 > n * (n - 1) || m < n - 1) {
//		cout << "NO\n";
//		return;
//	}
//	int d = k - 2;
//	if (d < 0) {
//		cout << "NO\n";
//	}
//	else if (d == 0) {
//		cout << (n == 1 ? "YES" : "NO") << '\n';
//	}
//	else if (d == 1) {
//		cout << (m * 2 == n * (n - 1) ? "YES" : "NO") << '\n';
//	}
//	else {
//		cout << "YES\n";
//	}
//}


//
//int t;
//int n, q, mod;
//int a[100005];
//int s[400005];
//int tim[400005];
//int add[400005];
//
//void up(int p) {
//	s[p] = (s[2 * p] + s[2 * p + 1]) % mod;
//}
//
//
//void addla(int p, int v, int n) {
//	s[p] = (s[p] + (n * v) % mod) % mod;
//	add[p] = (add[p] + v) % mod;
//}
//
//void timla(int p, int v) {
//	s[p] = (s[p] * v) % mod;
//	tim[p] = (tim[p] * v) % mod;
//	add[p] = (add[p] * v) % mod;
//}
//
//void down(int p, int ln, int rn) {
//	if (tim[p] != 1) {
//		timla(2 * p, tim[p]);
//		timla(2 * p + 1, tim[p]);
//		tim[p] = 1;
//	}
//	if (add[p]) {
//		addla(2 * p, add[p], ln);
//		addla(2 * p + 1, add[p], rn);
//		add[p] = 0;
//	}
//}
//
//void build(int l, int r, int p) {
//	tim[p] = 1;
//	if (l == r) {
//		s[p] = a[l];
//		return;
//	}
//	int m = (l + r) >> 1;
//	build(l, m, 2 * p);
//	build(m + 1, r, 2 * p + 1);
//	up(p);
//}
//
//void jia(int jl, int jr, int jv, int l, int r, int p) {
//	if (jl <= l && r <= jr) {
//		addla(p, jv, r - l + 1);
//		return;
//	}
//	int m = (l + r) >> 1;
//	down(p, m - l + 1, r - m);
//	if (jl <= m)jia(jl, jr, jv, l, m, 2 * p);
//	if (jr > m)jia(jl, jr, jv, m + 1, r, 2 * p + 1);
//	up(p);
//}
//
//void chen(int jl, int jr, int jv, int l, int r, int p) {
//	if (jl <= l && r <= jr) {
//		timla(p, jv);
//		return;
//	}
//	int m = (l + r) >> 1;
//	down(p, m - l + 1, r - m);
//	if (jl <= m)chen(jl, jr, jv, l, m, 2 * p);
//	if (jr > m)chen(jl, jr, jv, m + 1, r, 2 * p + 1);
//	up(p);
//}
//
//int ask(int jl, int jr, int l, int r, int p) {
//	if (jl <= l && r <= jr) {
//		return s[p];
//	}
//	int ans = 0;
//	int m = (l + r) >> 1;
//	down(p, m - l + 1, r - m);
//	if (jl <= m)ans = (ans + ask(jl, jr, l, m, 2 * p)) % mod;
//	if (jr > m)ans = (ans + ask(jl, jr, m + 1, r, 2 * p + 1)) % mod;
//	return ans;
//}
//
//void solve() {
//	cin >> n >> q >> mod;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	build(1, n, 1);
//	for (int i = 1, tmp, x, y, k; i <= q; i++) {
//		cin >> tmp >> x >> y;
//		if (tmp == 1) {
//			cin >> k;
//			chen(x, y, k, 1, n, 1);
//		}
//		else if (tmp == 2) {
//			cin >> k;
//			jia(x, y, k, 1, n, 1);
//		}
//		else {
//			cout << ask(x, y, 1, n, 1) << '\n';
//		}
//	}
//}



//int n;
//unordered_set<string> st;
//void solve() {
//	cin >> n;
//	string s;
//	for (int i = 1; i <= n; i++) {
//		cin >> s;
//		st.insert(s);
//	}
//	cout << st.size();
//}

//int n;
//int a[3000006];
//int ans[3000006];
//stack<int> st;
//void solve() {
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	for (int i = 1; i <= n; i++) {
//		while (!st.empty() && a[st.top()] < a[i]) {
//			ans[st.top()] = i;
//			st.pop();
//		}
//		st.push(i);
//	}
//	while (!st.empty()) {
//		ans[st.top()] = 0;
//		st.pop();
//	}
//	for (int i = 1; i <= n; i++) {
//		cout << ans[i] << ' ';
//	}
//}

//
//int n, m;
//int point[200005];
//int x[200005];
//int r[200005];
//int xx[2000005];
//int mx[2000005];
//int ans;
//
//void solve() {
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) {
//		cin >> x[i];
//		xx[i] = x[i];
//	}
//	int cnt = n;
//	for (int i = 1; i <= n; i++) {
//		cin >> r[i];
//		int tmp = r[i];
//		while (tmp) {
//			xx[++cnt] = x[i] + tmp;
//			xx[++cnt] = x[i] - tmp--;
//		}
//	}
//	sort(xx + 1, xx + 1 + cnt);
//	int tot = unique(xx + 1, xx + 1 + cnt) - xx - 1;
//
//	for (int i = 1; i <= n; i++) {
//		int index = lower_bound(xx + 1, xx + 1 + tot, x[i]) - xx;
//		if (r[i] > mx[index]) {
//			mx[index] = r[i];
//		}
//		int j = 1, high = r[i] - 1;
//		while (j < r[i] && high >= 0) {
//			if (high * high + j * j > r[i] * r[i])
//				high--;
//			int l = lower_bound(xx + 1, xx + 1 + tot, x[i] - j) - xx;
//			int rt = lower_bound(xx + 1, xx + 1 + tot, x[i] + j) - xx;
//			if (high > mx[l]) {
//				mx[l] = high;
//			}
//			if (high > mx[rt]) {
//				mx[rt] = high;
//			}
//			j++;
//		}
//	}
//	for (int i = 1; i <= tot; i++) {
//		ans++;
//		ans += mx[i] * 2;
//	}
//	cout << ans << '\n';
//	ans = 0;
//	for (int i = 0; i <= cnt + 1; i++) {
//		mx[i] = 0;
//	}
//}

//void up()
//
//int cx(int index, int l, int r, int p) {
//	if (l == r && r == index) {
//		return mx[p];
//	}
//	int m = (l + r) >> 1;
//	if (index <= m)return cx(index, l, m, 2 * p);
//	else return cx(index, m + 1, r, 2 * p + 1);
//}
//
//void xg(int index, int jv, int l, int r, int p) {
//	if (l == r && r == index) {
//		mx[p] = jv;
//		return;
//	}
//	int m = (l + r) >> 1;
//	if (index <= m)xg(index, jv, l, m, 2 * p);
//	else xg(index, jv, m + 1, r, 2 * p + 1);
//	up(p);
//}

//int x;
//int high;
//string s;
//
//bool check(int x) {
//	bool ok_1 = true;
//	int cnt = 0;
//	while (x) {
//		if ((x & 1) == 0) {
//			ok_1 = false;
//			s += '0';
//		}
//		else {
//			cnt++;
//			s += '1';
//		}
//		x >>= 1;
//	}
//	if (cnt == 1 || ok_1) {
//		return true;
//	}
//	else {
//		return false;
//	}
//}
//
//void solve() {
//	cin >> x;
//	int tmp = x;
//	if (check(x)) {
//		cout << "-1\n";
//		return;
//	}
//	x = tmp;
//	while (x) {
//		int ans = (x & (-x)) - 1;
//		if (ans + tmp > (ans ^ tmp) && (ans ^ tmp) + ans > tmp) {
//			cout << ans << '\n';
//			return;
//		}
//		x -= ans + 1;
//	}
//}



//int sum;
//int n;
//int a[200005];
//
//void solve() {
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	sum = a[1];
//	for (int i = 2; i <= n; i++) {
//		sum += a[i] - 1;
//	}
//	cout << sum << '\n';
//}


//int l, r, d, u;
//
//void solve() {
//	cin >> l >> r >> d >> u;
//	if (l == r && d == u && r == d && r != 0)
//		cout << "YES\n";
//	else
//		cout << "NO\n";
//}

